package practice1_100;

import java.util.ArrayList;
import java.util.List;

public class Offer26 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null||A==null) return false;
        List<TreeNode> list=new ArrayList<>();
        find(A,B,list);
        if(list.size()==0) return false;
        for (int i = 0; i < list.size(); i++) {
            TreeNode a= list.get(i);
            if(isStruct(a,B)) return true;//找到为true的结果，立马返回
        }
        return false;//最终找不到就是没有，返回false
    }

    public void find(TreeNode A, TreeNode B, List<TreeNode> list) {
        if (A==null) return;
        if(A.val== B.val) list.add(A);
        find(A.left,B,list);
        find(A.right,B,list);
    }

    public boolean isStruct(TreeNode A, TreeNode B){
        if(B==null) return true;//B在递归中变空了，说明之前都对应上了
        if(A==null&&B!=null) return false;//A递归中变空了，B不为空，说明对应不上
        if(A==null&&B==null) return true;//AB递归中都变空了，说明都遍历完了，返回true

        boolean a=A.val==B.val?true:false;//判断条件，值都是一致的，返回true
        return a&&isStruct(A.left,B.left)&&isStruct(A.right,B.right);//返回最终的结果值
    }

    public static void main(String[] args) {
       boolean c= new Offer26().isSubStructure(new TreeNode(3,new TreeNode(4,new TreeNode(1),new TreeNode(2)),new TreeNode(5)),new TreeNode(4,new TreeNode(1),null));
        System.out.println(c);
    }
}
